#include <iostream>
using namespace std;

int solution(int a, int b) {
  // write code here
  int tmp = 0;
  if (a % b != 0)
    tmp = 1;
  return a / b + tmp;
}

int main() {
  cout << (solution(10, 1) == 10) << endl;
  cout << (solution(10, 2) == 5) << endl;
  cout << (solution(10, 3) == 4) << endl;
  return 0;
}
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int solution(int n, int k) {
    int ans = 0,begin = k;
    while(n--){
        ans+=begin;
        begin+=k;
    }
    return ans;
}

int main() {
    std::cout << (solution(3, 1) == 6) << std::endl;
    std::cout << (solution(2, 2) == 6) << std::endl;
    std::cout << (solution(4, 3) == 30) << std::endl;
}
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int solution(int n, std::vector<int> A) {
  // Edit your code here
  stack<int> s;
  int ans = 0;
  for (int i = 0; i < n; i++) {
    while (!s.empty() && A[i] < A[s.top()]) {
      int a = A[s.top()];
      s.pop();
      int b = s.empty() ? i : i - s.top() - 1;
      ans = max(ans, a * b);
    }
    ans = max(ans, A[i]);
    s.push(i);
  }
  while (!s.empty()) {
    int a = A[s.top()];
    s.pop();
    int b = s.empty() ? n : n - s.top() - 1;
    ans = max(ans, a * b);
  }
  // cout << ans << endl;
  return ans;
}
// [7,8,19,10,6,22,10,5,2,14]
// 15,5,22,19,5,20,13,12,12
int main() {
  // Add your test cases here
  std::vector<int> A_case1 = std::vector<int>{1, 2, 3, 4, 5};
  std::cout << (solution(5, A_case1) == 9) << std::endl;
  std::vector<int> B_case1 = std::vector<int>{5, 4, 3, 2, 1, 6};
  std::cout << (solution(6, B_case1)) << std::endl;
  std::vector<int> C_case1 = std::vector<int>{4, 4, 4, 4};
  std::cout << (solution(4, C_case1)) << std::endl;
  std::vector<int> D_case1 = std::vector<int>{15, 5, 22, 19, 5, 20, 13, 12, 12};
  std::cout << (solution(9, D_case1)) << std::endl;
  return 0;
}
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int solution(int n) {
    // write code here
    int ans = 0;
    while(n != 1){
        ans += n/2;
        n = n -n/2;
    }
    return ans;
}

int main() {
    cout << (solution(7) == 6) << endl;
    cout << (solution(14) == 13) << endl;
    cout << (solution(1) == 0) << endl;

    return 0;
}
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int solution(std::string dna1, std::string dna2) {
  // Please write your code here
  int n1 = dna1.size(), n2 = dna2.size();
  vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 1000000));
  for (int i = 0; i <= n1; i++)
    dp[i][0] = i;
  for (int i = 0; i <= n2; i++)
    dp[0][i] = i;
  for (int i = 0; i < n1; i++) {
    for (int j = 0; j < n2; j++) {
      dp[i + 1][j + 1] = min(dp[i][j] + (dna1[i] != dna2[j]),
                             min(dp[i + 1][j] + 1, dp[i][j + 1] + 1));
      // if(dna1[i] != dna2[j])
      //     dp[i + 1][j + 1]++;
      // cout << dp[i + 1][j + 1] << ' ';
    }
    // cout << endl;
  }
  return dp[n1][n2];
}

int main() {
  //  You can add more test cases here
  std::cout << (solution("AGT", "AGCT")) << std::endl;
  // std::cout << (solution("AACCGGTT", "AACCTTGG")) << std::endl;
  // std::cout << (solution("ACGT", "TGC")) << std::endl;
  std::cout << (solution("CCCCACTGGAAGTCCTCCTAT", "T")) << std::endl; // 20
  return 0;
}
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int solution(const string& s) {
    int k = 0,u = 0;
    for(auto e : s){
        if(e == 'k'|| e == 'K')
            k++;
        else if(e == 'u'|| e == 'U')
            u++;
    }
    return min(k,u);
}

int main() {
    cout << (solution("AUBTMKAxfuu") == 1) << endl;
    cout << (solution("KKuuUuUuKKKKkkkkKK") == 6) << endl;
    cout << (solution("abcdefgh") == 0) << endl;
}
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
bool fun(int a,int b){
    return a > b;
}
int solution(int n, std::vector<int> nums) {
    sort(nums.begin(),nums.end(),fun);
    int pos = 0;
    // cout << nums[0] <<endl;
    for(int i = 1;i < n;i++){
        if(nums[i] != nums[i - 1])
            pos++;
        if(pos == 2)
            return nums[i];
    }
    return nums[0];
}

int main() {
    std::cout << (solution(3, {3, 2, 1})) << std::endl;
    std::cout << (solution(2, {1, 2})) << std::endl;
    std::cout << (solution(4, {2, 2, 3, 1})) << std::endl;
    return 0;
}
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int solution(int n, int l, int r, vector<int>& a) {
    int ans = 0;
    for(auto e : a){
        if(e%2 == 0 && e>= l &&e <= r)
            ans++;
    }
    return ans;
}

int main() {
    vector<int> a1 = {1, 2, 6, 8, 7};
    cout << (solution(5, 3, 8, a1) == 2) << endl;

    vector<int> a2 = {12, 15, 18, 9};
    cout << (solution(4, 10, 20, a2) == 2) << endl;

    vector<int> a3 = {2, 4, 6};
    cout << (solution(3, 1, 10, a3) == 3) << endl;
}
#include <iostream>
#include <string>
using namespace std;
int solution(std::string rgb) {
    // Please write your code here
    auto pos0 = rgb.find('(');
    auto pos1 = rgb.find(',',pos0);
    auto pos2 = rgb.find(',',pos1 + 1);
    auto pos3 = rgb.find(')',pos2);
    int a = stoi(rgb.substr(pos0 + 1,pos1 - 1));
    int b = stoi(rgb.substr(pos1 + 2,pos2 - 1));
    int c = stoi(rgb.substr(pos2 + 2,pos3 - 1));
    // cout <<a <<' '<<b <<' '<<c<<endl;
    return a*256*256+b*256+c;
}

int main() {
    //  You can add more test cases here
    std::cout << (solution("rgb(192, 192, 192)") == 12632256) << std::endl;
    std::cout << (solution("rgb(100, 0, 252)") == 6553852) << std::endl;
    std::cout << (solution("rgb(33, 44, 55)") == 2174007) << std::endl;
    return 0;
}
#include <iostream>
#include <vector>

// using namespace std;

int solution(std::vector<int> stocks) {
  // Please write your code here
  int ans = 0, n = stocks.size();
  if(n <= 1)  return 0;
  std::vector<int> f(n), g(n), h(n);
  g[0] = h[0] = 0;
  f[0] = -stocks[0];
  for (int i = 1; i < n; i++) {

    f[i] = std::max(f[i - 1],(i == 1 ? 0 :g[i - 2]) -stocks[i]); 
    g[i] = std::max(g[i - 1] ,f[i - 1] + stocks[i]);
    h[i] = g[i - 1];
  }
  return std::max(g[n - 1],g[n - 2]);
}

int main() {
  // You can add more test cases here
  std::cout << (solution({1, 2}) == 1) << std::endl;
  std::cout << (solution({2, 1}) == 0) << std::endl;
  std::cout << (solution({1, 2, 3, 0, 2}) == 3) << std::endl;
  std::cout << (solution({2, 3, 4, 5, 6, 7}) == 5) << std::endl;
  std::cout << (solution({1, 6, 2, 7, 13, 2, 8}) == 12) << std::endl;
  return 0;
}
#include <iostream>
#include <string>
#include <vector>
using std::min;
using std::cout;
using std::endl;
int solution(std::string dna1, std::string dna2) {
  int n1 = dna1.size(), n2 = dna2.size();
  std::vector<std::vector<int>> dp(n1 + 1, std::vector<int>(n2 + 1, 0));
  for (int i = 0; i <= n1; i++)
    dp[i][0] = i;
  for (int i = 0; i <= n2; i++)
    dp[0][i] = i;
  for (int i = 1; i <= n1; i++) {
    for (int j = 1; j <= n2; j++) {
      dp[i][j] = min(dp[i - 1][j - 1] + (dna1[i - 1] == dna2[j - 1] ? 0 : 1),
                     min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
        // cout << dp[i][j] <<' ';
    }
    // cout << endl;
  }
  return dp[n1][n2];
}

int main() {
  // You can add more test cases here
  std::cout << (solution("AGT", "AGCT") == 1) << std::endl;
  std::cout << (solution("", "ACGT") == 4) << std::endl;
  std::cout << (solution("GCTAGCAT", "ACGT") == 5) << std::endl;
  return 0;
}
#include <iostream>
#include <vector>

std::vector<int> solution(int n, int m, std::vector<std::vector<int>> citizens,
                          std::vector<std::vector<int>> locations) {
  // Please write your code here
  int pos = 0, a = 1000000;
  for (int i = 0; i < m; i++) {
    int tmp = 0;
    for (int j = 0; j < n; j++) {
      tmp += std::abs(citizens[j][0] - locations[i][0]);
      tmp += std::abs(citizens[j][1] - locations[i][1]);
    }
    if (tmp < a) {
        a = tmp;
        pos = i;
    }
  }
  return {locations[pos][0],locations[pos][1]};
}

bool vectorEqual(std::vector<int> a, std::vector<int> b) {
  if (a.size() != b.size()) {
    return false;
  }
  for (size_t i = 0; i < a.size(); ++i) {
    if (a[i] != b[i]) {
      return false;
    }
  }
  return true;
}

int main() {
  // You can add more test cases here
  std::vector<std::vector<int>> citizens1 = {
      {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
  std::vector<std::vector<int>> locations1 = {{3, 2}, {1, 0}, {0, 0}};

  std::vector<int> result = solution(4, 3, citizens1, locations1);
  std::cout << (vectorEqual(result, {1, 0})) << std::endl;
  return 0;
}
#include <iostream>
#include <vector>

using namespace std;

int solution(int Q, int V, vector<vector<int>> ships) {
    // Please write your code here
    vector<vector<int>> dp(Q + 1,vector<int>(V + 1));
    for(int i = 1;i <= Q;i++){
        int m = ships[i - 1][0];
        int v = ships[i - 1][1];
        int w = ships[i - 1][2];
        for(int j = 0;j <= V;j++){
            dp[i][j] = dp[i - 1][j];
            for(int k = 1;k <= m;k++){
                if(k*v <= j){
                    dp[i][j] = max(dp[i][j],dp[i - 1][j - k*v] + k*w);
                }
            }
        }
    }
    return dp[Q][V];
}

int main() {
    // You can add more test cases here
    vector<vector<int>> ships = {{2, 3, 2}, {3, 2, 10}};
    vector<vector<int>> ships2 = {{30, 141, 47}, {9, 258, 12}, {81, 149, 13}, {91, 236, 6}, {27, 163, 74}, {34, 13, 58}, {61, 162, 1}, {80, 238, 29}, {36, 264, 28}, {36, 250, 2}, {70, 214, 31}, {39, 116, 39}, {83, 287, 4}, {61, 269, 94}, {23, 187, 46}, {78, 33, 29}, {46, 151, 2}, {71, 249, 1}, {67, 76, 85}, {72, 239, 17}, {61, 256, 49}, {48, 216, 73}, {39, 49, 74}};
    cout << (solution(2, 10, ships) == 32) << endl;
    cout << (solution(23, 400, ships2) == 1740) << endl;

    return 0;
}
#include <iostream>
#include <vector>

int solution(int x, int y) {
  // Edit your code here
  int begin = 1, ans = 0;
  if(x == 0) 
    ans++;
  while (begin <= y) {
    for (int i = 1; i < 10; i++) {
      if (begin * i > y)
        break;
      if (begin * i >= x)
        ans++;
    }
    begin = begin * 10 + 1;
  }
  return ans;
}
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

long solution(int m,std::vector<int> w) {
    // write code here
    // std::vector<int> w
    sort(w.begin(),w.end());
    if(w[0] > m) 
        return 0;
    int ans = 1;
    int tmp = 1;
    for(int i = 1;i < w.size();i++){
        if(m >= w[i])
        {
            if(w[i] == w[i - 1])
                tmp++;
            else
                tmp = 1;
            ans = max(ans,tmp);
        }
    }
    return ans;
}
#include <iostream>
#include <set>
#include <vector>
using namespace std;
bool fun(int x)
{
    int a = -1,b = -1;
    while(x != 0){
        int tmp = x%10;
        x/=10;
        if(a == -1)
         a = tmp;
        else if(a == tmp){
            continue;
        }else if(b == -1){
            b = tmp;
        }else if(b == tmp){
            continue;
        }else{
            return false;
        }
    }
    return true;
}
int solution(int n) {
    int count = 0;
    for(int i = 1;i <= n;i++)
    {
        if(fun(i))
            count++;
    }
    return count;
}
int main() {
    cout << (solution(110) == 102) << endl;
    cout << (solution(1000) == 352) << endl;
    cout << (solution(1) )<< endl;
    return 0;
}
#include <iostream>
#include <vector>
using namespace std;

bool solution(int n, vector<int> a, int x, int y) {
    // write code here
    int c = 0,b = 0;
    for(int i = 0;i < n;i++){
        if(a[i] == x)
            c = i;
        else if(a[i] == y)
            b = i;
    }
    return abs(c - b) == 1;
}

int main() {
    cout << (solution(4, {1, 4, 2, 3}, 2, 4) == true) << endl;
    cout << (solution(5, {3, 4, 5, 1, 2}, 3, 2) == false) << endl;
    cout << (solution(6, {6, 1, 5, 2, 4, 3}, 5, 2) == true) << endl;
    return 0;
}
#include <iostream>
using namespace std;

int solution(int m, int x) {
    // write code here
    return x%m ? x%m : m;
}

int main() {
    cout << (solution(2, 3) == 1) << endl;
    cout << (solution(5, 17) == 2) << endl;
    cout << (solution(8, 2) == 2) << endl;
    cout << (solution(4, 4) == 4) << endl;
    return 0;
}
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

int solution(std::vector<int> a) {
    // write code here
    unordered_set<int>s;
    int n = a.size();
    vector<vector<int>> dp(n,vector<int>(n));
    for(int i = 0;i < n;i++){
        dp[i][i] = a[i];
        s.insert(dp[i][i]);
        for(int j = i - 1;j >= 0;j--){
            dp[i][j] = a[i] | dp[i - 1][j];
            s.insert(dp[i][j]);
        }
    }
    return s.size();
}
// 7  6  4
// 3  2
// 1
int main() {
    std::cout << (solution({1, 2, 4}) == 6) << std::endl;
    std::cout << (solution({5, 3, 8, 1}) == 8) << std::endl;
    std::cout << (solution({1, 1}) == 1) << std::endl;
    std::cout << (solution({7, 8, 9, 10, 11}) == 6) << std::endl;
    return 0;
}
#include <vector>
#include <iostream>
using namespace std;

bool solution(int n, int x, vector<int> a, vector<int> b) {
    // write code here
    int sum = 0,t_sum = 0;;
    for(int i = 0;i < n;i++)
    {
        if(b[i] < 60) return false;
        sum += a[i]*b[i];
        t_sum += a[i];
    }
    return sum >= t_sum * x;
}

int main() {
    cout << (solution(4, 75, {4, 3, 2, 1}, {80, 70, 90, 60}) == true) << endl;
    cout << (solution(3, 85, {3, 2, 5}, {90, 85, 88}) == true) << endl;
    cout << (solution(5, 80, {2, 2, 3, 1, 4}, {78, 80, 79, 85, 88}) == true) << endl;
    cout << (solution(6, 70, {4, 3, 2, 1, 2, 3}, {60, 72, 65, 90, 85, 95}) == true) << endl;
    cout << (solution(4, 90, {2, 2, 2, 2}, {89, 91, 92, 85}) == false) << endl;
    return 0;
}
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int solution(int n, vector<vector<int>>& a) {
    // write code here
    int ans = 0;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            ans += (abs(a[i][j]-a[j][i]));
        }
    }
    return ans;
}

int main() {
    vector<vector<int>> a1 = {{1, 2}, {3, 4}};
    cout << (solution(2, a1) == 2) << endl;

    vector<vector<int>> a2 = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    cout << (solution(3, a2) == 16) << endl;

    vector<vector<int>> a3 = {{1, 1, 1, 1}, {2, 2, 2, 2}, {3, 3, 3, 3}, {4, 4, 4, 4}};
    cout << (solution(4, a3) == 20) << endl;
}
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

long long solution(vector<int> a, vector<int> b) {
    // write code here
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    int ans = 0;
    for(int i = 0;i < a.size();i++){
        ans += abs(a[i] -b[i]);
    }
    return ans;
}

int main() {
    vector<int> a1 = {2, 1, 3, 2}, b1 = {5, 2, 4, 2};
    vector<int> a2 = {1, 4, 6}, b2 = {2, 5, 7};
    vector<int> a3 = {1, 9, 6}, b3 = {2, 5, 7};
    
    cout << (solution(a1, b1) == 5) << endl;
    cout << (solution(a2, b2) == 3) << endl;
    cout << (solution(a3, b3) == 4) << endl;
    
    return 0;
}
#include <iostream>
#include <vector>
using namespace std;

int solution(int n, vector<int> a, vector<int> b) {
    // write code here
    int suma = 0,sumb = 0;
    for(int i = 0;i < n;i++){
        suma += a[i],sumb += b[i];
    }
    int ans = 0;
    for(int i = 0;i < n;i++){
        ans = max(ans,(suma - a[i])^sumb);
        ans = max(ans,(sumb - b[i])^suma);
    }
    return ans;
}

int main() {
    cout << (solution(3, {1, 2, 3}, {3, 2, 1}) == 5) << endl;
    cout << (solution(4, {4, 5, 6, 7}, {7, 8, 9, 10}) == 51) << endl;
    cout << (solution(5, {10, 20, 30, 40, 50}, {50, 40, 30, 20, 10}) == 248) << endl;
    return 0;
}
	
#include <iostream>
#include <vector>
#include <stack>
bool solution(int n, std::vector<int> a, std::vector<int> b) {
    int c = 0;
    std::stack<int> s;
    for(int i = 0;i < n;i++){
        s.push(a[i]);
        while(!s.empty() && s.top() == b[c])
        {
            s.pop();
            c++;
        }
    }
    return s.empty();
}

int main() {
    std::cout << (solution(3, std::vector<int>{1, 2, 3}, std::vector<int>{1, 2, 3}) == true) << std::endl;
    std::cout << (solution(3, std::vector<int>{1, 2, 3}, std::vector<int>{3, 2, 1}) == true) << std::endl;
    std::cout << (solution(3, std::vector<int>{1, 2, 3}, std::vector<int>{3, 1, 2}) == false) << std::endl;
    return 0;
}
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int solution(int n) {
    int a = 2,ans = 2;
    for(;a*a <= n;a++){
        if(n/a == n/(a - 1))
            continue;
        if(n/a == a)
            ans++;
        else
            ans+=2;
    }
    return ans;
}

int main() {
    std::cout << (solution(5) == 3) << std::endl;
    std::cout << (solution(7) == 4) << std::endl;
    std::cout << (solution(10) == 5) << std::endl;

    return 0;
}
#include <iostream>
#include <vector>
using std::vector;
using std::max;
int solution(int n, std::vector<int> weights, std::vector<int> values, int m) {
    //vector<vector<int>> dp(m + 1);
    vector<int> dp(m + 1);
    for(int i = 0;i < n;i++){
        for(int j = m;j >= weights[i];j--){
            dp[j] = max(dp[j - weights[i]] + values[i],dp[j]);
        }
    }
    // for(int i = 0;i <=m;i++){
    //     std::cout << dp[i] << ' '; 
    // }
    // std::cout << std::endl;
    return dp[m];
}

int main() {
    std::cout << (solution(3, {2, 1, 3}, {4, 2, 3}, 3) == 6) << std::endl;
    std::cout << (solution(4, {1, 2, 3, 2}, {10, 20, 30, 40}, 5) == 70) << std::endl;
    std::cout << (solution(2, {1, 4}, {5, 10}, 4) == 10) << std::endl;
}
#include <iostream>

int fun(int c){
    if(c == 0)
        return 0;
    return fun(c>>1) *2 + (c%2 == 0);
}
int solution(int N) {
    // write code here
    if(N == 0) return 1;
    return fun(N); // Placeholder return
}

int main() {
    std::cout << (solution(5)) << std::endl;
    std::cout << (solution(10) == 5) << std::endl;
    std::cout << (solution(0) == 1) << std::endl;
    return 0;
}
#include <vector>
#include <iostream>
#include <string>
bool fun(int a,int i){
    int tmp = 1;
    while(tmp <= i)
        tmp<<=1;
    while(a >= i){
        if(((a-i)%tmp) == 0)
            return false;
        a>>=1;
    }
    return true;
}
bool solution(std::string s, int n) {
    // write code here
    int a = 0;
    for(auto &e : s){
        a *=2;
        a +=(e-'0');
    }
    for(int i = 1;i <= n;i++){
        if(fun(a,i)){
            std::cout << a <<' ' <<i << std::endl;
            return false;
        }
    }
    return true; // Placeholder return
}

int main() {
    std::cout << (solution("0110", 3) == true) << std::endl;
    std::cout << (solution("1001", 4) == false) << std::endl;
    std::cout << (solution("00010011", 5) == true) << std::endl;
    return 0;
}
#include <iostream>

int solution(int x) {
  // write code here
  int ans = 0;
  for (int a = 1; a <= 20; a++) {
    for (int b = 1; b <= 20; b++) {
      for (int c = 1; c <= 20; c++) {
        for (int d = 1; d <= 20; d++) {
            if(a*d - b*c == x)
                ans++; 
        }
      }
    }
  }
  return ans;
}

int main() {
  std::cout << (solution(2) == 682) << std::endl;
  std::cout << (solution(-3) == 567) << std::endl;
  std::cout << (solution(0) == 1360) << std::endl;
}
#include <iostream>
#include <vector>

int solution(std::vector<int>& fruits) {
    // write code here
    int n = fruits.size(),left = 0,mid = 0,right = 0,ans = 0;
    for(;right < n;right++)
    {
        if(fruits[right] != fruits[left] && fruits[right] != fruits[mid])
        {
            if(mid == left)
                mid = right;
            else{
                left = mid;
                mid = right;
            }
        }
        if(fruits[right] != fruits[mid])
            fruits[left] = fruits[mid],mid = right;
        ans = std::max(ans,right - left + 1);
    }
    // std::cout << ans << std::endl;
    return ans;
}

int main() {
    std::vector<int> fruits1 = {1, 2, 1, 2};
    std::vector<int> fruits2 = {2, 0, 1, 2, 2};
    std::vector<int> fruits3 = {6,1,13,1,9,9};
    
    std::cout << (solution(fruits1) == 4) << std::endl;
    std::cout << (solution(fruits2) == 3) << std::endl;
    std::cout << (solution(fruits3) == 3) << std::endl;
    return 0;
}
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;
int solution(std::vector<int> nums, int k) {
  int n = nums.size();
  vector<int> sum(n + 1);
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    sum[i] = sum[i - 1] + nums[i - 1];
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        if((sum[i] - sum[j - 1]) %k == 0)
        {
            cout << sum[i] - sum[j - 1] << ' ';
            ans++;
        }
    }
  }
  cout << endl;
  cout <<ans << endl;
  return ans; // Placeholder return
}

int main() {
  std::cout << (solution({4, 5, 0, -2, -3, 1}, 5) == 7) << std::endl;
  std::cout << (solution({1, 2, 3}, 3) == 3) << std::endl;
  std::cout << (solution({-1, 2, 9}, 2) == 2) << std::endl;
  return 0;
}
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;
int solution(std::vector<int> nums, int k) {
  int n = nums.size();
  vector<int> sum(n + 1);
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    sum[i] = sum[i - 1] + nums[i - 1];
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        if((sum[i] - sum[j - 1]) %k == 0)
        {
            cout << sum[i] - sum[j - 1] << ' ';
            ans++;
        }
    }
  }
  cout << endl;
  cout <<ans << endl;
  return ans; // Placeholder return
}

int main() {
  std::cout << (solution({4, 5, 0, -2, -3, 1}, 5) == 7) << std::endl;
  std::cout << (solution({1, 2, 3}, 3) == 3) << std::endl;
  std::cout << (solution({-1, 2, 9}, 2) == 2) << std::endl;
  return 0;
}
#include <iostream>
#include <vector>

int solution(int x, int y) {
    int ans = 0;
    while(y != x){
        if(y < x || y%2 == 1)
        {
            y++;
            ans++;
        }else{
            y/=2;
            ans++;
        }
    }
    return ans; // Placeholder return
}

int main() {
    std::cout << (solution(2, 3) == 2) << std::endl;
    std::cout << (solution(4, 7) == 2) << std::endl;
    std::cout << (solution(3, 66) == 9) << std::endl;
    return 0;
}
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int solution(int A, int B, int C, int D) {
    int a = A/B,b = C/D;
    if(a == b && A%B == 0 && C % D == 0)
        return a;
    return -1;
}

int main() {
    std::cout << (solution(4, 2, 6, 3) == 2) << std::endl;
    std::cout << (solution(8, 4, 15, 5) == -1) << std::endl;
    std::cout << (solution(9, 3, 12, 4) == 3) << std::endl;
}
#include <iostream>
#include <vector>
#include <cassert>
const int N = 1e9+7;
int solution(int n, const std::vector<int>& a) {
    int ans = 0;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < i;j++){
            ans = (ans + (a[i]^a[j])*(n - i)*(j + 1)) % N;
        }
    }
    // std::cout << ans << std::endl;
    return ans; // Placeholder
}

int main() {
    std::vector<int> a1 = {2, 3, 1, 2};
    std::cout << (solution(4, a1) == 28) << std::endl;

    std::vector<int> a2 = {5, 6, 7};
    std::cout << (solution(3, a2) == 10) << std::endl;

    std::vector<int> a3 = {1, 10};
    std::cout << (solution(2, a3) == 11) << std::endl;

    std::vector<int> a4 = {1, 2, 4, 8, 16};
    std::cout << (solution(5, a4) == 402) << std::endl;

    return 0;
}
#include <vector>
#include <iostream>
using namespace std;

vector<vector<int>> solution(vector<vector<int>> a) {
    // write code here
    for(auto & e : a){
        for(auto& ee : e){
            if(ee %2 == 0)
                ee*= 3;
        }
    }
    return a;
}

int main() {
    cout << (solution({{1, 2, 3}, {4, 5, 6}}) == vector<vector<int>>{{1, 6, 3}, {12, 5, 18}}) << endl;
    cout << (solution({{7, 8, 9}, {10, 11, 12}}) == vector<vector<int>>{{7, 24, 9}, {30, 11, 36}}) << endl;
    cout << (solution({{2, 4}, {6, 8}}) == vector<vector<int>>{{6, 12}, {18, 24}}) << endl;
    return 0;
}
#include <string>
#include <iostream>
#include <vector>
using namespace std;

int solution(string s) {
    // write code here
    int n = s.size(),ans = 1;
    vector<vector<bool>> dp(n,vector<bool>(n));
    for(int i = 0;i < n;i++){
        for(int j = i - 1;j >=0;j--){
            if(s[i] == s[j] && (i - j < 3 || dp[i - 1][j + 1] == true))
            {
                ans = max(ans,i - j + 1);
                dp[i][j] = true;
            }
        }
    }
    return ans;
}

int main() {
    cout << (solution("abcbadb") == 5) << endl;
    cout << (solution("ababacab") == 5) << endl;
    cout << (solution("racecarwk") == 7) << endl;
    return 0;
}
#include <iostream>
#include <vector>

int solution(int n, int T, int H, std::vector<int> t, std::vector<int> h, std::vector<int> a) {
    // write code here
    std::vector<std::vector<int>> dp(T + 1,std::vector<int>(H + 1));
    for(int i = 0;i < n;i++){
        for(int j = T;j >= t[i];j--){
            for(int k = H;k >= h[i];k--)
            {
                dp[j][k] = std::max(dp[j][k],dp[j - t[i]][k - h[i]] + a[i]);
            }
        }
    }
    for(int i = 0;i <=  T;i++){
        for(int j = 0;j <= H ;j++){
            std::cout << dp[i][j] << ' ';
        }
        std::cout << std:: endl;
    }
    return dp[T][H];
}

int main() {
    std::cout << (solution(2, 2, 2, {1, 3}, {3, 1}, {3, 4}) == 0) << std::endl;
    std::cout << (solution(3, 5, 5, {2, 1, 3}, {1, 3, 2}, {10, 7, 8}) == 18) << std::endl;
    std::cout << (solution(1, 3, 3, {4}, {4}, {5}) == 0) << std::endl;
}
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int solution(int n, vector<int>& a, int x, int y) {
    // write code here
    int sum = 0,len = 0;
    if(x > y) swap(x,y);
    for(int i = 0;i < n;i++){
        sum += a[i];
        if(i + 2 > x && i < y - 1){
            len += a[i];
        }
    }
    return min(len,sum - len);
}

int main() {
    vector<int> a1 = {1, 2, 2};
    cout << (solution(3, a1, 2, 3) == 2) << endl;
    
    vector<int> a2 = {1, 2, 2};
    cout << (solution(3, a2, 1, 3) == 2) << endl;
    
    vector<int> a3 = {3, 5, 7, 2};
    cout << (solution(4, a3, 1, 4) == 2) << endl;
    
    return 0;
}
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int solution(int n, int K, vector<int> a) {
    int left = 0,right = 0,ans = 0;
    unordered_map<int,int>window;
    for(;right < n;right++)
    {
        window[a[right]]++;
        while(window.size() > K)
        {
            if(--window[a[left]] == 0)
                window.erase(a[left]);
            left++;
        }
        ans  = max(ans,right - left + 1);
    }
    return ans;
}

int main() {
    cout << (solution(8, 3, {1, 2, 3, 2, 1, 4, 5, 1}) == 5) << endl;
    cout << (solution(7, 2, {1, 2, 2, 2, 1, 1, 3}) == 6) << endl;
    cout << (solution(6, 4, {4, 5, 4, 6, 7, 8}) == 5) << endl;
    return 0;
}
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int solution(const std::string& s) {
    // write code here
    std::stack<int> a;
    int ans = 0;
    for(auto &e : s){
        if(e == '(')
            a.push('(');
        else if(e == ')'){
            if(a.empty()){
                ans++;
            }else{
                a.pop();
            }
        }
    }
    // cout << ans <<' ' << a.size() << endl;
    return ans + a.size(); // placeholder return
}

int main() {
    std::cout << (solution("())") == 1) << std::endl;
    std::cout << (solution("(((") == 3) << std::endl;
    std::cout << (solution("()") == 0) << std::endl;
    std::cout << (solution("()))((") == 4) << std::endl;
    return 0;
}
#include <vector>
#include <iostream>

int solution(std::vector<int> nums) {
    int n = nums.size();
    int count = 0;

    // 使用三重循环来遍历所有可能的三元组，并计算满足条件的三元组的数量
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                if ((nums[i] & nums[j] & nums[k]) == 0) {
                    count++;
                }
            }
        }
    }

    return count;
}

int main() {
    std::cout << (solution({2, 1, 3}) == 12) << std::endl;
    std::cout << (solution({0, 2, 5}) == 25) << std::endl;
    std::cout << (solution({1, 2, 4}) == 24) << std::endl;
    return 0;
}
#include <iostream>
#include <string>

int solution(const std::string& s) {
    // write code here
    int ans = 0;
    for(auto e : s){
        if( e == '0') ans++;
        else if( e == '6') ans++;
        else if( e == '9') ans++;
        else if( e == '8') ans+=2;
    }
    return ans;
}

int main() {
    std::cout << (solution("1234567890") == 5) << std::endl;
    std::cout << (solution("8690") == 5) << std::endl;
    std::cout << (solution("1111") == 0) << std::endl;
}
#include <iostream>
#include <vector>
#include <string>

using namespace std;
bool fun(int n){
    int a = n;
    cout << a << ' ';
    while(a > 0){
        cout << a << ' ';
        if(a%10 == 0)
        {    a/=10;
            continue;
        }
        if(n%(a%10)){
            a/=10;
        }else{
            return true;
        }
    }
    return false;
}
int solution(int N) {
    cout << N << ' ';
    while(N){
        if(fun(N))
        {
            return N;
        }
        N--;
    }
    return 0;
}

int main() {
    std::cout << (solution(499) == 497) << std::endl;
    std::cout << (solution(1000) == 1000) << std::endl;
    std::cout << (solution(785) == 785) << std::endl;
}
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int solution(int L, int R) {
    // write code here
    int ans = 0;
    for(int i = L;i <= R - 2;i++)
    {
        if(i%4 < 2)
            return 1;
    }
    return 0;
}
//  1  3
//  4  6
//  5  7
//  8  10
// 1011 11
// 1101 13
int main() {
    std::cout << (solution(2, 7) == 1) << std::endl;
    std::cout << (solution(1, 4) == 1) << std::endl;
    std::cout << (solution(5, 10) == 1) << std::endl;
}
#include <iostream>
#include <vector>

using namespace std;
int solution(std::vector<int> time) {
  // write code here
  vector<int> dp(10);
  int ans = 0;
  for (auto e : time) {
    e = e % 10;
    ans += dp[(10 - e)%10];
    dp[e]++;
  }
  return ans; // Placeholder return
}

int main() {
  std::cout << (solution({3, 2, 15, 1, 4}) == 0) << std::endl;
  std::cout << (solution({10, 20, 30}) == 3) << std::endl;
  std::cout << (solution({7, 3, 5, 5, 10})) << std::endl;
  return 0;
}
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int solution(int n, vector<int> a) {
    // write code here
    sort(a.begin(),a.end());
    int begin = 0,ans = 0;
    for(int i = 0;i < n;i++){
        if(a[i] >= begin){
            begin = a[i] + 1;
        }else{
            ans += begin++ - a[i];
        }
    }
    return ans;
}

int main() {
    cout << (solution(5, {1, 1, 2, 3, 3}) == 5) << endl;
    cout << (solution(6, {4, 4, 4, 5, 5, 6}) == 11) << endl;
    cout << (solution(7, {10, 20, 10, 30, 40, 30, 20}) == 3) << endl;
    return 0;
}
#include <iostream>
#include <string>
using namespace std;
bool fun(char a,char b){
    if(abs(a - b) == abs('a' - 'A') || a == b)
        return true;
    return false;
}
int solution(string s) {
    // write code here
    int ans = 0;
    for(int i = 1;i < s.size();i++){
        if(fun(s[i - 1],s[i]))
            ans++;
    }
    return ans;
}

int main() {
    cout << (solution("aABbbC") == 3) << endl;
    cout << (solution("XYZxyZ") == 0) << endl;
    cout << (solution("AaBbCc") == 3) << endl;
    return 0;
}
#include <iostream>
#include <vector>

int solution(int n, std::vector<int> a) {
    // write code here
    int ans = 1,left = 0,right = 1;
    for(;right < n;right++){
        if(abs(a[right] - a[right - 1]) >= 2){
            left = right;
        }
        ans = std::max(right - left + 1,ans);
    }
    return ans;
}

int main() {
    std::cout << (solution(5, {2, 4, 2, 3, 2}) == 3) << std::endl;
    std::cout << (solution(6, {1, 2, 2, 3, 4, 1}) == 5) << std::endl;
    std::cout << (solution(7, {5, 5, 6, 7, 7, 6, 5}) == 7) << std::endl;
}
#include <iostream>
#include <vector>
#include <string>

using namespace std;
int N  = 1e7 + 9;
int solution(int n, std::vector<int> a, std::vector<int> b) {
    int ans = 0;
    vector<vector<int>> dp(n + 1,vector<int>(3));
    dp[0][0] = 1;
    for(int i = 1;i <= n;i++){
        for(int j = 0;j < 3;j++){
            dp[i][j] = dp[i - 1][(j - a[i - 1] + 99)% 3] + dp[i - 1][(j - b[i - 1] + 99)% 3]; 
        }
    }
    // for(int j = 0;j < 3;j++){
    // for(int i = 0;i <=n;i++){
    //     cout <<dp[i][j] <<' '; 
    // }
    // cout << endl;}
    return dp[n][0]%N; // Placeholder return
}

int main() {
    std::cout << (solution(3, {1, 2, 3}, {2, 3, 2}) == 3) << std::endl;
    std::cout << (solution(4, {3, 1, 2, 4}, {1, 2, 3, 1}) == 6) << std::endl;
    std::cout << (solution(5, {1, 2, 3, 4, 5}, {1, 2, 3, 4, 5}) == 32) << std::endl;
    return 0;
}